//
// Description: 457. 环形数组是否存在循环
// Created by Loading on 2021/8/7.
//

#include <bits/stdc++.h>

using namespace std;

bool circularArrayLoop(vector<int> &nums) {
    int n = nums.size();
    // 寻找下一个下标的方法，注意负数
    auto next = [&](int index) {
        return ((index + nums[index]) % n + n) % n;
    };

    // 遍历每个点
    for (int i = 0; i < n; ++i) {
        // 已被遍历过
        if (nums[i] == 0) {
            continue;
        }
        // 定义快慢指针下标
        int slow = i, fast = next(i);
        // 同方向判断，注意需要判断 next(fast) 方向，防止漏掉状态提前返回
        while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(fast)] > 0) {
            // 快慢指针相遇
            if (slow == fast) {
                // 判断循环长度是否为 1，循环长度为 1 时，slow与next(slow)相等
                if (slow != next(slow)) {
                    return true;
                } else {
                    break;
                }
            }
            slow = next(slow);
            fast = next(next(fast));
        }

        // 将路径设置为 0
        int current = i;
        while (nums[current] * nums[next(current)] > 0) {
            int temp = current;
            nums[current] = 0;
            current = next(temp);
        }
    }

    return false;
}

int main() {
    vector<int> nums = {-2, 1, -1, -2, -2};
    cout << circularArrayLoop(nums) << endl;
}